% Notes taken for the course COMP 553 - Algorithmic Game Thoery.
% Taught by Professor Adrian Vetta in Fall 2011, at McGill University
%
% Shen Chen Xu <shenchenxu@gmail.com>
\documentclass{article}%

\usepackage[left=1.2in,right=1.2in]{geometry}
\usepackage[T1]{fontenc}
\usepackage{kpfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{enumerate}
\usepackage{color}
\usepackage{multirow}
\usepackage[bookmarks,bookmarksopen]{hyperref}

\pdfpagewidth 8.5in
\pdfpageheight 11.0in

\newtheoremstyle{mythm}% name
  {\baselineskip}% space above
  {\baselineskip}% space below
  {}% body font
  {0pt}% indent amount
  {\bfseries}% theorem head font
  {:}% punctuation after theorem head
  { }% space after theorem head
  {}% theorem head spec

\theoremstyle{mythm}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem*{algorithm}{Algorithm}%[subsection]
\newtheorem*{example}{Example}%[subsection]
\newtheorem*{definition}{Definition}%[subsection]
\newtheorem*{corollary}{Corollary}%[subsection]
\newtheorem*{remark}{Remark}

\newcommand{\abs}[1]{\left\lvert#1\right\rvert}
\newcommand{\norm}[1]{\left\lVert#1\right\rVert}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\prob}[1]{\mathrm{P}\left\{#1\right\}}
\newcommand{\expect}[1]{\mathrm{E}\left\{#1\right\}}

\begin{document}
\sloppy

\title{COMP 553 - Algorithmic Game Theory}
\author{Shen Chen Xu}
\maketitle

\tableofcontents

\section{Games}

Loosely speaking, a game is any iteration between more than $2$ agents/players
with non-identical objective. Specifically, each player $i$ has a preference
ranking $\succ_i$ on the potential outcomes $O_1,O_2,\dots\in\mathcal{O}$ of
the game. The preference lists should satisfy:
\begin{enumerate}
  \item (Completeness) For all $O,O'\in\mathcal{O}$, exactly one of $O\succ O'$
    or $O'\succ O$ is true.
  \item (Transitivity) If $O\succ O'$ and $O'\succ O''$, then $O\succ O''$.
\end{enumerate}
Sometimes, rather than working with preference lists, we assume that each
player $i$ has an \emph{utility function} $u_i:\mathcal{O}\to\reals$ which
assigns a score to each outcome such that
\begin{align*}
  u_i\left(O\right)>u_i\left(O'\right)\iff O\succ_i O',\;
  \forall O,O'\in\mathcal{O}.
\end{align*}
But a utility function is a \emph{much} stronger assumption then a preference
list since it adds scale and allows complex mathematical operations such as
expectation and calculus. The central assumption in game theory (and economics)
is that agents aim to maximize their utility function. Such agents are called
\emph{rational}.

\begin{remark}
  Rational agents are self-interested in that the \emph{only} care about their
  own utility function. However, this does not mean that they don't care about
  the other agents, because characteristics such as altruism or maliciousness
  can be encoded into the utility function (or preference list).
\end{remark}

\section{Nash Equilibrium}

What happens when players simultaneously try to maximize their utility? For
example, we describe the game ``Hawk-Dove'' (or ``chicken'') in the normal
form:
\begin{align*}
  \begin{array}{c|cc}
    & H & D \\ \hline
    H & \left(0,0\right) & \left(5,1\right) \\
    D & \left(1,5\right) & \left(4,4\right)
  \end{array}
\end{align*}
The strategy pair $(D,D)$ seems to be the best, but it's not stable:
player $1$ (or player $2$) can do better by switching to $H$. Therefore $H$ is
called a \emph{best response} for player $1$ given player $2$ is playing $D$.
If all players are playing a best response given the other players' strategies,
then we are at the \emph{Nash equilibrium}, and no player wants to change
strategy. In the example, $(H,D)$ or $(D,H)$ are the Nash
equilibriums. Such a stable solution is typically assumed to be the outcome of
the game, but if there are more than one Nash equilibrium, we will need more
information about the game.
\\

Consider the game of rock-paper-scissor:
\begin{align*}
  \begin{array}{c|ccc}
    & R & P & S \\ \hline
    R & \left(0,0\right) & \left(-1,1\right) & \left(1,-1\right) \\
    P & \left(1,-1\right) & \left(0,0\right) & \left(-1,1\right) \\
    S & \left(-1,1\right) & \left(1,-1\right) & \left(0,0\right)
  \end{array}
\end{align*}
Note that there are no \emph{pure strategy} Nash equilibrium. A \emph{mixed
strategy} puts probabilities on the strategy choices, for example,
$(R:0.1,P:0.6,S:0.3)$. So a pure strategy is a special case of mixed
strategies. In the above example, $(R:\frac13,P:\frac13,S:\frac13)$
is a mixed strategy Nash equilibrium.
\\

\section{Domination}

Consider the prisoner's dilemma:
\begin{align*}
  \begin{array}{c|cc}
    & C & D \\ \hline
    C & \left(-9,-9\right) & \left(0,-10\right) \\
    D & \left(-10,0\right) & \left(-1,-1\right)
  \end{array}
\end{align*}
Note that the payoffs of player $1$ in row $C$ are always better than the ones
in row $D$ no matter what strategy player $2$ plays. Thus player $1$ should
never play $D$ and we say that $C$ strictly dominates $D$. Same goes for player
$2$ and the only rational outcome is $(C,C)$. This is a Nash
equilibrium in dominating strategy.
\\

However the other three outcomes in this game are \emph{Pareto optimal}. An
outcome is Pareto optimal if there is no outcome that has at least as high
payoffs for all players and more than one player is strictly better off. Note
that the Nash equilibrium misses them all!

\section{Social Choice Theory}

How should society make decisions based upon the individual preferences of its
members? We will model this as an election. We have $n$ voters and $k$
candidates ($n$ members, $k$ possible actions). Voter $i$ has a preference list
$\succ_i$ for the candidates. For example:
\begin{gather*}
  a\succ_1c\succ_1b\\
  b\succ_2a\succ_2c\\
  c\succ_3b\succ_3a\\
\end{gather*}
Let $\Pi$ be the set of all permutations (rankings) of the candidates and let
$[k]\equiv\{1,2,\dots,k\}$. We may want to combine the
preference lists to give:
\begin{enumerate}
  \item A single winner, $f:\Pi^n\to[k]$.
  \item A complete ordering, $g:\Pi^n\to\Pi$.
\end{enumerate}
We call $f$ the social choice function and we call $g$ the social welfare
function. Consider the following example with 100 voters:
\begin{center}
  49 votes $a\succ c\succ b$,\\
  46 votes $b\succ a\succ c$,\\
  5 votes $c\succ b\succ a$.
\end{center}
There are several ways to run an election. \emph{Plurality} chooses the
candidate with the most top rankings, thus $a$ would be the winner in this
example. In \emph{Borda count}, candidates gets points for his/her positions in
each voter's list, the one with most points wins. For example, we can give
three points for being in first position, two points for second position and
one point for last position, the winner is again $a$. In \emph{majority}
voting, candidate $a$ beats candidate $b$ if the majority prefers $a$ to $b$.
However, as in our example, there can be a \emph{conflict cycle} in which there
is no winner: $a$ beats $c$ with votes 95 to 5, $c$ beats $b$ 54 to 46 and $b$
beats $a$ 51 to 49.

Other than producing a winner, we look for other properties in an election
mechanism. What if the 5 voters with preference $c\succ b\succ a$ lied and vote
$b\succ c\succ a$? Then $b$ wins in plurality instead of $a$, and the 5 votes
are happier with this outcome. So plurality can be ``gamed''. We say that a
social choice function $f$ is \emph{strategically manipulable} if
$\exists\succ_1,\succ_2,\dots,\succ_n\in\Pi$ and $\succ_i'\in\Pi$ for some $i$
where
\begin{align*}
  f\left(\succ_1,\succ_2,\dots,\succ_i,\dots,\succ_n\right)&=a,\\
  f\left(\succ_1,\succ_2,\dots,\succ_i',\dots,\succ_n\right)&=b,
\end{align*}
and voter $i$ prefers $b$ to $a$ ($b\succ_i a$). A social choice function that
is not manipulable is called \emph{incentive compatible}. For example, a
mechanism in which truth telling is a dominant strategy, like majority voting with
two candidates or dictatorship (the dictator obviously tells the truth, and the
others might as well also tell the truth since it doesn't matter anyway).
Unfortunately, dictatorship is pretty much all we can have in general.

\subsection{Gibbard-Satterthwaite Theorem}

\begin{theorem}[Gibbard-Satterthwaite theorem]
  \label{gibbard-satterthwaite-thm}
  Any incentive compatible social choice function $f$ is a dictatorship,
  provided that there are three or more candidates and $f$ is onto the set of
  candidates.
\end{theorem}

Before proving this, we consider a different (but ``stronger'') result for
social welfare functions.

\subsection{Arrow's Impossibility Theorem}

Here are two conditions that we would naturally want
from a social welfare function $g$:
\begin{enumerate}
  \item \emph{Unanimity}: If every voter prefer $a$ to $b$, then $g$ should output
    $a\succ_gb$.
  \item \emph{Independence of Irrelevant Alternatives (IIA)}: The relative
    positions of $a$ and $b$ under the preference list output by $g$ depends
    only on the relative positions of $a$ and $b$ in the voters' preference
    lists. More formally, if $\forall i,a\succ_ib\iff a\succ_i'b$, then
    $g(\succ_1,\dots,\succ_n)$ and
    $g(\succ_1',\dots,\succ_n')$ give the same ordering of $a$ and
    $b$.
\end{enumerate}

\begin{remark}
  IIA is fundamental in economics in general as it lies at the heart of
  ``rationality''.
\end{remark}

\begin{lemma}[Pairwise neutrality]
  \label{pairwise-neutrality}
  Let $g$ be a social welfare function satisfying IIA. Consider two pairs
  $(a,b)$ and $(\alpha,\beta)$. If $\forall
  i,a\succ_ib\iff\alpha\succ_i\beta$, then $a\succ_gb\iff\alpha\succ_gb$.
\end{lemma}

\begin{proof}
  We compare the set of preference lists $\succ_1,\dots,\succ_n$ to another set
  $\succ_1',\dots,\succ_n'$ that is easy to analyze. Without loss of
  generality, assume that $g$ ranks $a\succ_gb$. For each voter $i$, move
  $\alpha$ just above $a$ and move $\beta$ just below $b$ in $\succ_i$. This
  can always be done without changing the ordering of $\alpha$ and $\beta$
  since $a\succ_ib\iff\alpha\succ_i\beta$. Then, by unanimity, $g$ must rank
  $\alpha\succ_g'a$ and $b\succ_g'\beta$. By our previous assumption,
  $a\succ_gb$, thus by IIA, $a\succ_g'b$. Therefore, we have that
  $\alpha\succ_g'a\succ_g'b\succ_g'\beta$. By transitivity,
  $\alpha\succ_g'\beta$, and by IIA, $\alpha\succ_g\beta$ when voting with the
  original preference lists.

\end{proof}

\begin{theorem}[Arrow's Impossibility Theorem]
  \label{arrow-impossibility-theorem}
  Any social welfare function $g$ that satisfies unanimity and IIA is a
  dictator ship (if the number of candidates $k\ge3$).
\end{theorem}

\begin{proof}
  Let $g$ be any social welfare function that satisfies unanimity and IIA. We
  want to show that there exists a voter $d$ who is a dictator for the relative
  ordering of $\alpha$ and $\beta$, for any $\alpha,\beta$, under the social
  welfare function $g$.

  Take any candidates $a$ and $b$, and an arbitrary collection of preference
  lists $\succ_1,\dots,\succ_n$ provided $\forall i,b\succ_ia$. One by one, we
  create a new preference list $\succ_i'$ from $\succ_i$ simply by moving $a$
  above $b$:
  \begin{align*}
    \begin{array}{c|c}
      d & \text{preference lists} \\ \hline
      0 & \succ_1,\succ_2,\succ_3,\dots,\succ_n \\
      1 & {\color{red}\succ_1'},\succ_2,\succ_3,\dots,\succ_n \\
      2 & {\color{red}\succ_1',\succ_2'},\succ_3,\dots,\succ_n \\
      3 & {\color{red}\succ_1',\succ_2',\succ_3},\dots,\succ_n \\
      \vdots & \vdots \\
      n & {\color{red}\succ_1',\succ_2',\succ_3',\dots,\succ_n'} \\
    \end{array}
  \end{align*}
  Note that by unanimity, we have $b\succ_ga$ when $d=0$ and $a\succ_gb$ when
  $d=n$. Therefore, $\exists0<d<n$ such that
  \begin{align*}
    {\color{red}\succ_1',\succ_2',\dots,\succ_{d-1}'},
    \succ_d,\succ_{d+1},\dots,\succ_n
    \qquad\text{gives}\qquad b\succ_ga,
  \end{align*}
  and
  \begin{align*}
    {\color{red}\succ_1',\succ_2',\dots,\succ_{d-1}',\succ_d'},
    \succ_{d+1},\dots,\succ_n
    \qquad\text{gives}\qquad a\succ_gb.
  \end{align*}
  Let's write out the relative ordering of $a$ and $b$ at time $d-1$ and $d$.
  At time $d-1$, we have that:
  \begin{align*}
    \begin{array}{c|ccccccc}
      \text{voter} & 1 & \cdots & d-1 & d & d+1 & \cdots & n \\ \hline
      \multirow{2}{*}{\text{Preference list}}
      & a & \cdots & a & b & b & \cdots & b \\
      & b & \cdots & b & a & a & \cdots & a \\ \hline
      \text{result} & \multicolumn{7}{c}{b\succ_ga}
    \end{array}
    \tag{P1}
  \end{align*}
  At time $d$:
  \begin{align*}
    \begin{array}{c|ccccccc}
      \text{voter} & 1 & \cdots & d-1 & d & d+1 & \cdots & n \\ \hline
      \multirow{2}{*}{\text{Preference list}}
      & a & \cdots & a & a & b & \cdots & b \\
      & b & \cdots & b & b & a & \cdots & a \\ \hline
      \text{result} & \multicolumn{7}{c}{a\succ_gb}
    \end{array}
    \tag{P2}
  \end{align*}

  Now take any candidates $\alpha$ and $\beta$. Without loss of generality,
  assume that $\alpha\succ_d\beta$. Create a new set of preference lists such
  that every other voter has an arbitrary ordering of $\alpha$ and $\beta$.
  Add a new candidates $c\ne\alpha,\beta$ (we can remove $c$ later and by IIA,
  the ranking of $\alpha$ and $\beta$ will stay the same) such that:
  \begin{enumerate}
    \item $c$ is at the top of the ranking for voters $1,\dots,d-1$.
    \item $c$ is at the bottom of the ranking for voters $d+1,\dots,n$.
    \item $c$ is ranked between $\alpha$ and $\beta$ by voter $d$.
  \end{enumerate}
  The situation is then
  \begin{align*}
    \begin{array}{c|ccccccc}
      \text{voter} & 1 & \cdots & d-1 & d & d+1 & \cdots & n \\ \hline
      \multirow{5}{*}{\text{Preference list}}
      & c & \cdots & c \\
      & & & & \alpha \\
      & \alpha/\beta & \cdots & \alpha/\beta & c & \alpha/\beta & \cdots & \alpha/\beta \\
      & & & & \beta \\
      & & & & & c & \cdots & c \\
    \end{array}
    \tag{P2}
  \end{align*}
  Observe that the pair $(c,\alpha)$ has the same pattern as in
  (P1), therefore $\alpha\succ_gc$ by lemma (\ref{pairwise-neutrality}).
  Similarly, $(c,\beta)$ has the same pattern as (P2), and thus
  $c\succ_g\alpha$. By transitivity, we have that $\alpha\succ_g\beta$. The
  $\alpha,\beta$ rankings of voters $i\ne d$ were arbitrary, so $d$ is a
  dictator and $g$ is a dictatorship.

\end{proof}

Now we come back and prove the Gibbard-Satterthwaite Theorem
(theorem (\ref{gibbard-satterthwaite-thm})) using this result. Recall that we
want our social choice function to be incentive compatible. However, the
following concept is equivalent but easier to apply. A social choice function
is \emph{monotone} if
\begin{align*}
  f\left(\succ_1,\dots,\succ_i,\dots,\succ_n\right)&=a,\\
  f\left(\succ_1,\dots,\succ_i',\dots,\succ_n\right)&=b
\end{align*}
implies that $a\succ_ib$ and $b\succ_i'a$.

\begin{theorem}
  $f$ is monotone $\iff$ $f$ is incentive compatible.
\end{theorem}

(TODO: prove this)

Given a preference list $\succ_i$, let $\succ_k^S$ be the preference list
obtained by moving $S\subseteq[k]$ to the top of the ranking,
maintaining the ordering within $S$. We will assume that our social choice
function is onto the set of candidates, in other words we don't consider
candidates that cannot possibly win.

\begin{lemma}
  \label{top-candidates-win-lemma}
  For any $\succ_1,\dots,\succ_n$ and any $S\subseteq[k]$. If $f$ is
  an incentive compatible social choice function, then
  $f(\succ_1^S,\dots,\succ_n^S)\in S$.
\end{lemma}

\begin{proof}
  Take some $a\in S$, since $f$ is onto, $\exists\succ_1',\dots,\succ_n'$ such
  that $f(\succ_1',\dots,\succ_n')=a$. We now replace $\succ_i'$ by
  $\succ_i^S$ one by one as follows:
  \begin{align*}
    f\left(\succ_1',\succ_2',\dots,\succ_n'\right)&=w_0,\\
    f\left({\color{red}\succ_1^S},\succ_2',\dots,\succ_n'\right)&=w_0,\\
    f\left({\color{red}\succ_1^S,\succ_2^S},\dots,\succ_n'\right)&=w_1,\\
    &\vdots\\
    f\left({\color{red}\succ_1^S,\succ_2^S,\dots,\succ_n^S}\right)&=w_n.
  \end{align*}
  We claim that $\forall i,w_i\in S$ and we already know that $w_0=a$. For a
  contradiction, we assume that there exists some $i$ such that $w_i\in S$ and
  $w_{i+1}\notin S$. From time $i$ to time $i+1$, only the voter $i+1$ changes
  preference. So by monotonicity,
  \begin{align*}
    w_i\succ_{i+1}'w_{i+1},\\
    w_{i+1}\succ_{i+1}^Sw_i.
  \end{align*}
  But we assumed that $w_i\in S$ and $w_{i+1}\notin S$, this is a contradiction.

\end{proof}

\begin{proof}[Proof of the Gibbard-Satterthwaite Theorem]
  We will prove the Gibbard-Satterthwaite theorem by showing that it's a
  special case of Arrow's impossibility theorem. To use Arrow's theorem, we
  turn $f$ into a social welfare function $g$ as follows:
  \begin{align*}
    \forall a,b\in\left[k\right],\quad
    a\succ_gb\iff
    f\left(\succ_1^{\left\{a,b\right\}},\dots,\succ_1^{\left\{a,b\right\}}\right)=a.
  \end{align*}

  We first show that $g$ is a social welfare function. Completeness is trivial,
  we still need transitivity. For a contradiction, let $S=\{a,b,c\}$
  where $g$ gives a conflict cycle $a\succ_gc\succ_gb\succ_ga$. Without loss of
  generality, assume that
  \begin{align*}
    f\left(\succ_1^S,\succ_2^S,\dots,\succ_n^S\right)&=w_0,\\
    f\left({\color{red}\succ_1^{\left\{a,b\right\}}},\succ_2',\dots,\succ_n'\right)&=w_0,\\
    f\left({\color{red}\succ_1^{\left\{a,b\right\}},\succ_2^{\left\{a,b\right\}}},\dots,\succ_n'\right)&=w_1,\\
    &\vdots\\
    f\left(
    {\color{red}\succ_1^{\left\{a,b\right\}},\succ_2^{\left\{a,b\right\}},\dots,\succ_n^{\left\{a,b\right\}}}
    \right)&=w_n.
  \end{align*}
  But $a$ and $b$ are in the same order for $\succ_i^S$ and
  $\succ_i^{\{a,b\}}$ for all $i$. Thus by monotonicity,
  $\forall i,w_i\ne b$. By lemma (\ref{top-candidates-win-lemma}),
  $\forall i,w_i=a$. Thus $a\succ_gb$, this is a contradiction, so no conflict
  cycle exists.

  We now show that $g$ satisfies unanimity and IIA, then by Arrow's theorem,
  $g$ is a dictatorship. Suppose we have $a\succ_ib$ for all $i$. Then, $g$
  gives $a\succ_gb$ because
  \begin{align*}
    f\left( 
    \succ_1^{\left\{a,b\right\}},\dots,\succ_n^{\left\{a,b\right\}}
    \right)
    =
    f\left( 
    \left(\succ_1^{\left\{a,b\right\}}\right)^{\left\{a\right\}},
    \dots,
    \left(\succ_n^{\left\{a,b\right\}}\right)^{\left\{a\right\}}
    \right)
    =
    a.
  \end{align*}
  Now suppose that $\succ_i$ and $\succ_i'$ rank $a$ and $b$ in the same order
  for all $i$. Then consider the following:
  \begin{align*}
    f\left(
    \succ_1^{\left\{a,b\right\}},
    \succ_2^{\left\{a,b\right\}},
    \dots,
    \succ_n^{\left\{a,b\right\}}
    \right)&=x_0,
    \\
    f\left(
    {\color{red}
    \succ_1'^{\left\{a,b\right\}}},
    \succ_2^{\left\{a,b\right\}},
    \dots,
    \succ_n^{\left\{a,b\right\}}
    \right)&=x_1,
    \\
    f\left(
    {\color{red}
    \succ_1'^{\left\{a,b\right\}},
    \succ_2'^{\left\{a,b\right\}}},
    \dots,
    \succ_n^{\left\{a,b\right\}}
    \right)&=x_2,
    \\
    &\vdots
    \\
    f\left(
    {\color{red}
    \succ_1'^{\left\{a,b\right\}},
    \succ_2'^{\left\{a,b\right\}},
    \dots,
    \succ_n'^{\left\{a,b\right\}}}
    \right)&=x_n.
  \end{align*}
  By monotonicity, $x_i$ never changes. Therefore, $g$ satisfies the IIA
  condition.
  
  This implies that $f$ is also a dictatorship. To see this, suppose that $f$
  is not a dictatorship. In other words, there exists a set of preference lists
  $\succ_1,\dots,\succ_n$ such that $f$ does not output the top choice of
  player $i$, for any $i$. Let $a$ be the top choice of $i$ and let $b$ be the
  choice of $f$, consider the preference lists
  $\succ_1^{\{a,b\}},\dots,\succ_n^{\{a,b\}}$. $f$ still
  output $b$ by monotonicity, thus in the corresponding social welfare
  function, we have that $b\succ_a$. But recall that player $i$ ranked $a$
  higher than $b$, so we can find a counterexample showing that $i$ is not a
  dictator, for all $i$.

\end{proof}

This result seems to exclude the possibility of incorporating incentive
compatibility into social choice theory. Mechanism design attempts to get
around this via ``transferable utility'', i.e., money.

\section{Rationality}

\emph{Rational man} (or \emph{economic man}) has a preference list $\succ$ over
the set of outcomes $\mathcal{O}=\{O_1,O_2,\dots\}$. Whenever he has a choice
to make over a subset $\mathcal{S}\subseteq\mathcal{O}$, he \emph{always}
choose the $\succ$-optimal outcome $O^*\in\mathcal{S}$ such that $\forall
O'\in\mathcal{S}$, $O^*\succ O'$ and $O^*\ne O'$. In other words:
\begin{enumerate}
  \item He always knows what is feasible (the set $\mathcal{S}$).
  \item He always knows his preference.
  \item He can optimize in any circumstance (computation is not an issue).
  \item He always make the same choice given any description of $\mathcal{S}$.
\end{enumerate}

Rational man may not exist, but that does not matter, if agents act
\emph{as if} they are rational (Friedman, 1953).

(TODO: Cobb-Douglas utility function example?)

Suppose that an agent uses a choice function $f$ when making choice. We say
that $f$ satisfies the IIA condition if
\begin{align*}
  \forall\mathcal{S}'\subset\mathcal{S}\subseteq\mathcal{O},
  f\left(\mathcal{S}\right)\in\mathcal{S}'
  \Rightarrow
  f\left(\mathcal{S}'\right)=f\left(\mathcal{S}\right)
\end{align*}

\subsection{Rationality and Independence of Irrelevant Alternatives}

\begin{theorem}
  $f$ is IIA $\iff$ the agent is rational.
\end{theorem}

\begin{proof}
  It is pretty clear that rationality implies IIA. To show the other direction,
  we assume that $f$ is IIA and we need
  \begin{enumerate}[(1)]
    \item Agent has a preference list $\succ$.
    \item Agent always make a $\succ$-opitmal choice.
  \end{enumerate}

  To obtain (1), we need completeness and transitivity. We can easily get
  completeness by setting $a\succ b\iff f(\{a,b\})=a$. Now suppose that
  $a\succ b$ (i.e. $f(\{a,b\})=a$) and $b\succ c$ (i.e. $f(\{b,c\})=b$). Then
  we have that $f(\{a,b,c\})=a$ since $f$ is IIA. This implies $f(\{a,c\})=c$
  and we have transitivity.

  To obtain (2), take $\mathcal{S}\subseteq\mathcal{O}$, let
  $f(\mathcal{S})=O^*$. For any $O'\in\mathcal{S}$, $O'\ne O^*$, we have that
  $f(\{O^*,O'\})=O^*$ by IIA, therefore $O^*\succ O'$.

\end{proof}

\section{Mechanism Design}

Can we truthfully implement a social choice function? Rather than rank the
outcomes by a preference list, we assume each player $i$ has a value function
$v_i$ defined for each outcome. We also allow payments (of utilities) to be
made between the players and with the mechanism.

\subsection{Second Price Auction (Vickrey Auction)}

Suppose that we want to implement the following social choice function
\begin{align*}
  \max_{S\in\mathcal{O}}\sum_iv_i\left(S\right),
\end{align*}
known as the \emph{maximum social welfare} or \emph{economic efficiency}. We
will model this as an auction. We have one good to sell and $k$ bidders. Bidder
$i$ has a valuation $v_i$ of the good. We assume that the players have
quasi-linear utility function $u_i=v_i-p_i$ if bidder $i$ gets the item and
pays $p_i$ (otherwise it's just $-p_i$). The second price auction is a sealed
bid auction in which the highest bid wins but only pays the second highest bid.
This auction has two nice properties: incentive compatibility and individual
rationality (truthful bidders always have non-negative utility).

\begin{theorem}
  The second price auction satisfies incentive compatibility and individual
  rationality.
\end{theorem}

\begin{proof}
  Take player $i$ with value $v_i$. Consider the other bids
  $\mathbf{b}_{-i}\equiv\{b_j\}_{j\ne i}$ and let
  $\hat{b}=\max_{j\ne i}b_j$. If $v_i>\hat{b}$, any bid $b_i>\hat{b}$ wins and
  gives utility $v_i-\hat{b}>0$, and any bid $b_i\le\hat{b}$ loses and give
  zero utility. Thus bidding truthfully is a best response. If $v_i<\hat{b}$,
  any bid $b_i>\hat{b}$ gives a negative utility, and any bid $b_i\le\hat{b}$
  gives zero utility. Again, bidding truthfully is a best response. Therefore,
  this mechanism is incentive compatible. The individual rationality property
  is trivial.
\end{proof}

\subsection{VCG Mechanism}

Can we generalize the second price auction to more complicated auctions (and
social choice functions)? After trying out a few examples, we notice that if
the winner of the auction drops out, then our objective function, the social
welfare, will drop by the utility of that player. Therefre, each player has
utility equal to his/her marginal contribution to the social choice function.
This is the key idea of the VCG (Vickrey-Clark-Groves) mechanism:
\begin{center}
  \fbox{
  \begin{minipage}{10cm}
    Set the price $p_i$ of player $i$ such that the utility $u_i$ equals to the
    marginal contribution.
  \end{minipage}
  }
\end{center}
or equivalently:
\begin{center}
  \fbox{
  \begin{minipage}{10cm}
    Set the price $p_i$ of player $i$ to be equal to the total damage that
    player $i$ does to the other players by taking part.
  \end{minipage}
  }
\end{center}

\begin{theorem}
  A VCG mechanism is incentive compatible.
\end{theorem}

\begin{proof}
  Take player $i$ with value $v_i$ and bids $\mathbf{b}_{-i}=\{b_j\}_{j\ne i}$.
  We consider three cases:
  \begin{enumerate}
    \item Suppose that player $i$ bids truthfully with $b_i=v_i$, the mechanism
      outputs the outcome $S^T$, and the social welfare, according to what the
      mechanism knows, is
      \begin{align*}
        v_i\left(S^T\right)+\sum_{j\ne i}b_j\left(S^T\right)
        \equiv
        v_i\left(S^T\right)+A.
      \end{align*}
    \item Suppose that player $i$ lies and bids $b_i\ne v_i$, the mechanism
      outputs the outcome $S^L$, and the social welfare, according to what the
      mechanism knows, is
      \begin{align*}
        b_i\left(S^L\right)+\sum_{j\ne i}b_j\left(S^L\right)
        \equiv
        b_i\left(S^L\right)+B.
      \end{align*}
    \item Suppose that player $i$ doesn't participate, the mechanism outputs
      the outcome $S^{-i}$, and the social welfare, according to what the
      mechanism knows, is
      \begin{align*}
        \sum_{j\ne i}b_j\left(S^{-i}\right)\equiv C.
      \end{align*}
  \end{enumerate}
  Since we have a VCG mechanism, the price charged to player $i$ and his/her
  utility in each case are:
  \begin{enumerate}
    \item
      \begin{align*}
        p_i^T&=C-A,\\
        u_i^T&=v_i\left(S^T\right)-\left(C-A\right).
      \end{align*}
    \item
      \begin{align*}
        p_i^L&=C-B,\\
        u_i^L&=v_i\left(S^L\right)-\left(C-B\right).
      \end{align*}
  \end{enumerate}
  We want to show that $u_i^T\ge u_i^L$. Consider the following:
  \begin{align*}
    &&u_i^T&\ge u_iL
    \\\iff&&
    v_i\left(s^T\right)-\left(C-A\right)
    &\ge
    v_i\left(s^L\right)-\left(C-B\right)
    \\\iff&&
    v_i\left(s^T\right)+A
    &\ge
    v_i\left(s^L\right)+B
    \\\iff&&
    v_i\left(s^T\right)+\sum_{j\ne i}b_j\left(S^T\right)
    &\ge
    v_i\left(s^L\right)+\sum_{j\ne i}b_j\left(S^L\right).
  \end{align*}
  But the social welfare that the mechanism maximizes when given the input
  $(v_i,\mathbf{b}_{-i})$ is exactly the LHS of the last inequality.

\end{proof}

Allowing transferable utility (money), we can implement truthfully a social
choice function that maximizes the social welfare. It can be shown that VCG
mechanisms are the \emph{only} way to implement such a social choice function
(Section 9.5 in Algorithmic Game Theory).

\subsection{Applications of VCG Mechanism}

Here are some examples:
\begin{enumerate}
  \item \emph{Single item auction:} VCG gives the second price auction.
  \item \emph{Bilateral trade:} There is a seller who owns an item and values
    it at $v_s$. THere is a buyer who values it at $v_b$. To maximize social
    welfare, we must have: $\text{trade}\iff v_s\le v_b$. VCG does this, but
    what are the prices?
    \begin{enumerate}[(i)]
      \item $v_s\le v_b$, VCG says trade and sets the prices as follows:
        \begin{center}
          \begin{tabular}{|c|c|c|}
            \hline
            & Contribution & Price \\\hline
            Seller & $c_s=v_b-0$ & $0-p_s=c_s=v_b$, thus $p_s=v_b$ \\
            Buyer & $c_b=v_b-v_s$ & $v_b-p_b=c_b=v_b-v_s$, thus $p_b=v_s$
            \\\hline
          \end{tabular}
        \end{center}

      \item $v_s>v_b$, VCG says no trade and sets the prices as follows:
        \begin{center}
          \begin{tabular}{|c|c|c|}
            \hline
            & Contribution & Price \\\hline
            Seller & $c_s=v_s-0$ & $v_s-p_s=c_s=v_s$, thus $p_s=0$ \\
            Buyer & $c_b=v_s-v_s$ & $0-p_b=c_b=0$, thus $p_b=0$
            \\\hline
          \end{tabular}
        \end{center}
    \end{enumerate}
    Note that the mechanism is subsidising the trade! Since VCG is the only
    incentive compatible mechanism for maximizing social welfare, no incentive
    compatible mechanism can avoid subsidisingthe trade.

  \item \emph{Public project:} The government is deciding whether to build a
    bridge at cost $C$. The value of the bridge to citizen $i$ is $v_i$. The
    government doesn't want citizens with $v_i>0$ or $v_i<0$ to exagerate to
    help to win the argument. Let's assume that $v_i\ge0$ for all $i$, and
    treat the government as a ``player'' with value $-C$ if bridge is built and
    $0$ otherwise. Consider the contribution of the citizen $i$:
    \begin{align*}
      c_i&=
      \left\{
      \begin{array}{ll}
        v_i & \text{if $\sum_{j\ne i}v_j\ge C$ (building the bridge anyway)}
        \\
        \left(\sum_jv_j\right)-C & \text{if $\sum_{j\ne i}v_j<C$ and
        $\sum_jv_j\ge C$ (citizen $i$ is critical)}
        \\
        0 & \text{if $\sum_jv_j<C$ (not building the bridge anyway)}
      \end{array}
      \right.
      \intertext{The price charged to citizen $i$ in each case is then:}
      p_i&=
      \left\{
      \begin{array}{l}
        0 \\ C-\sum_{j\ne i}v_j \\ 0
      \end{array}
      \right.
    \end{align*}
    Note that a citizen pays if and only if he/she is critical, i.e.
    $v_i\ge\sum_jv_j-C\ge 0$. Let $\mu\equiv\sum_jv_j-C$. Observe that
    $\sum_jv_j=C+\mu$. So if one player is critical, then the maximum revenue
    is at most $C$, and if there are two critical players, the maximum revenue
    is at most $C-\mu$. But non-critical players pays nothing! The ideal
    scenario would be $\sum_jv_j=C$, but often most or all players are not
    critical. Thus VCG mechanism typically gives a budget deficit.

  \item \emph{Combinatorial auction:} Suppose that we have $n$ (different)
    items $I=\{1,2,\dots,n\}$ to sell. There are $k$ bidders and they bid
    $b_i(S)$ on any subset $S\subseteq I$. What does VCG do? The mechanism
    outputs an allocation $(S_1,S_2,\dots,S_n)$ such that
    $S_i\cap S_j=\emptyset,\;\forall i\ne j$. The contribution of player $i$ is
    \begin{align*}
      c_i=\sum_jb_j\left(s^*\right)
      -
      \max_{\substack{\{S'_j\}_{j\ne i}\\\{S'_j\}\text{ feasible}}}
      \sum_{j\ne i}b_j\left(S'_j\right).
    \end{align*}
    Thus the price charged to player $i$ is
    \begin{align*}
      p_i
      &=
      v_i\left(S_i\right)-c_i
      \\&=
      \max_{\substack{\{S'_j\}_{j\ne i}\\\{S'_j\}\text{ feasible}}}
      \sum_{j\ne i}b_j\left(S'_j\right)
      -
      \sum_{j\ne i}b_j\left(s^*\right).
    \end{align*}
\end{enumerate}

\subsection{Relevation Principle}

We saw that VCG is an incentive compatible mechanism that \emph{implements} the
social choice function
\begin{align*}
  f:T_1\times T_2\times\cdots\times T_n\to\mathcal{O}
\end{align*}
where $T_i$ is the set of possible ``types'' for agent $i$ and $f$ outputs
$S\in\mathcal{O}$ that maximizes $\sum_iv_i(S)$. By ``implement'' we mean that
for all valuations $v_1,\dots,v_n$, there exists equilibrium bids
$b_1,\dots,b_n$ such that $VCG(b_1,\dots,b_n)=f(v_1,\dots,v_n)$. VCG is also a
\emph{direct} (revelation) mechanism, since agents simple declare their types
to the mechanism (truthfully or not), and VCG happens to be truthful.

So for social welfare function $f$, VCG implements $f$ via a direct and
truthful mechanism. What if $f$ is a different function? For example, we might
want to maximize fairness: $\max_{S\in\mathcal{O}}\min_iu_i(S)$, or revenue:
$\max_{S\in\mathcal{O}}\sum_ip_i(S)$. Can we still implement these? Can we do
it using a direct mechanism?

In a indirect mechanism, agents have a wider set of actions/strategies
$a_i(t_i)$ so
\begin{align*}
  f:A_1\times A_2\times\cdots\times A_n\to\mathcal{O},
\end{align*}
where $A_i$ consists of the set of actions $a_i(t_i)$, $t_i\in T_i$. But we
will see that allowing indirect mechanism is not helpful.

\begin{theorem}[Relevation Principle]
  If a social choice function $f$ can be implemented by an indirected mechanism
  $M^i$, then it can be implemented by a direct and truthful mechanism $M^d$
  with the same payments.
  \label{revelation-principle}
\end{theorem}

\begin{proof}[Proof sketch]
  The mechanism will ``lies'' for the players, so the player might as well tell
  the truth.
\end{proof}

\subsection{VCG Practicalities}

(TODO)

\subsection{Revenue Equivalence}

In this section, we are interested in guarantees under expectaion (Baysian Nash
equilibrium) rather than worst case guarantees (dominant strategies).
Previously, agents only know their own types. Now we assume that they also know
the distributions of the other players' types.

For example, we have two risk-neutral bidders whose values are uniformly
distributed on $[0,1]$. We claim that in a first price auction, it is a Baysian
Nash equilibrium to bid $b_i=v_i/2$.  Assume that player $2$ bids $v_2/2$.
Consider player $1$ (note that $b_1\le1/2$):
\begin{align*}
  u_1(b_1)
  &=
  \left(v_1-b_1\right)\prob{\text{player 1 wins with $b_1$}}
  \\&=
  \left(v_1-b_1\right)\prob{b_1\ge b_2}
  \\&=
  \left(v_1-b_1\right)\prob{b_1\ge\frac{v_2}2}
  \\&=
  \left(v_1-b_1\right)\prob{v_2\le 2b_1}
  \\&=
  \left(v_1-b_1\right)2b_1
  \\
  \frac{d}{db_1}u_1(b_1)
  &=
  2v_1-4b_1
  \\
  \frac{d}{db_1}u_1(b_1)
  &=
  0
  \\
  b_1&=\frac{v_1}2.
\end{align*}
What's the expected revenue? Note that
\begin{align*}
  \expect{\max\left(b_1,b_2\right)}
  &=
  \frac12\expect{\max\left(v_1,v_2\right)}.
\end{align*}
Let $Z=\max\left(v_1,v_2\right)$,
\begin{align*}
  \expect{Z}
  &=
  \int_0^11-F\left(z\right)dz
  \\&=
  \int_0^11-z^2dz
  \\&=
  \left.z-\frac13z^3\right|_0^1
  \\&=
  \frac23.
\end{align*}
Thus the expected revenue is $1/3$.

In a second price auction, the players bid truthfully, and the expected revenue
also turns out to be $1/3$!

\begin{theorem}[Revenue Equivalence Theorem]
  Suppose that we have $n$ risk neutral bidders with valuations from a density
  function $f(v)$ on $[0,1]$. Any auction with the following properties has the
  same expected revenue:
  \begin{enumerate}
    \item Given the same expected utility to bidders $v=0$.
    \item Assigns the good the the highest bidder (or to the $k$ highest
      bidders if you have $k$ copies of the good).
  \end{enumerate}
  \label{revenue-equivalence}
\end{theorem}

\begin{proof}
  The relevation principle still applies if we want a Baysian Nash equilibrium
  rather than a dominant strategy implementation. Therefore we can assume
  truthfulness.
\end{proof}

\end{document}
